package com.leetcode.algorithms.one.problem5;

import org.junit.Test;

public class LongestPalindromicSubstring {
    @Test
    public void run(){
        String s = "abacdecxcedasdd";
//        String s = "#a#b#a#c#d#e#c#";
        System.out.println(longestPalindrome(s));
    }

    public String longestPalindrome(String s) {
        char[] array = s.toCharArray();
        char[] chars = new char[array.length*2+1];
        for(int i=0;i<array.length;i++){
            chars[2*i]='#';
            chars[2*i+1]=array[i];
        }
        chars[2*array.length]='#';
        int max=0;
        int index = 0;

        for(int i=1;i<chars.length;i++){
            int currMax = getCurrentMax(chars,i);
            if(currMax>max){
                max=currMax;
                index=i;
            }
        }

//        String result = new String(chars,index-max,2*max+1);
        StringBuilder sb=new StringBuilder();
        for(int i=index-max;i<index+max;i++){
            if(chars[i]!='#')
                sb.append(chars[i]);

        }

        return sb.toString();
    }

    public int getCurrentMax(char[] chars,int i){
        int max=0;
        int len1 = i;
        int len2 = chars.length - i-1;
        int out = len1<len2?len1:len2;
        int k=1;

//        int index=i;
        while(out>0&&chars[i-k]==chars[i+k]){
            max++;
            out--;
            k++;
        }

        return max;
    }
}
